Ordinal recursive bounds for Higman's theorem
Identifieur interne : 002470 ( Istex/Checkpoint ); précédent : 002469; suivant : 002471Ordinal recursive bounds for Higman's theorem
Auteurs : E. A. Cichon [France] ; E. Tahhan Bittar [France]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 1998.
English descriptors
- Teeft :
- Bittarl, Cartesian product, Characterise functions, Cichon, Computer science, Constant sequence, Constant subsequence, Constructive proof, Control function, Control information, Decomposition lemma, Finite alphabet, First paragraph, Fundamental sequence, Fundamental sequences, General case, Hardy hierarchies, Hardy hierarchy, Hierarchy, Higman, Higman function, Induction hypothesis, Initial part, Last component, Lecture notes, Lemma, Lemma dejine, Lemma guarantee, Length hierarchies, Limit ordinal, Majorisation properties, Mathematical logic, Naive argument, Natural number, Natural numbers, Ordinal, Ordinal term, Ordinal terms, Passenger sequence, Peano arithmetic, Present context, Present paper concerns theorem, Principal sequence, Principal subsequence, Product space, Product spaces, Recursive, Recursive functions, Same controls, Smallest relation, Subrecursive hierarchies, Subsequence, Such sequences, Tahhan, Tahhan bittar, Tahhan bittaritheoretical computer science, Tahhan bittarl, Terminal element, Terminal elements, Theoretical computer science, Totality, Transfinite induction, Worst case situation.
Abstract
Abstract: The present paper concerns Higman's theorem for strings generated over a finite alphabet. We give a constructive proof of this theorem and we construct and characterise functions which bound the lengths of bad sequences. These bounding functions are described by ordinal-recursive definitions and their characterisation is achieved with reference to Hardy hierarchies of numbertheoretic functions.
Url:
DOI: 10.1016/S0304-3975(97)00009-1
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
ISTEX:2D8DBE8A7739405BF206BBC00B509404FF4EFBBCLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Ordinal recursive bounds for Higman's theorem</title><author><name sortKey="Cichon, E A" sort="Cichon, E A" uniqKey="Cichon E" first="E. A." last="Cichon">E. A. Cichon</name></author><author><name sortKey="Bittar, E Tahhan" sort="Bittar, E Tahhan" uniqKey="Bittar E" first="E. Tahhan" last="Bittar">E. Tahhan Bittar</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:2D8DBE8A7739405BF206BBC00B509404FF4EFBBC</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1016/S0304-3975(97)00009-1</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-HGQTGKT2-T/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000A63</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000A63</idno><idno type="wicri:Area/Istex/Curation">000A57</idno><idno type="wicri:Area/Istex/Checkpoint">002470</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002470</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Ordinal recursive bounds for Higman's theorem</title><author><name sortKey="Cichon, E A" sort="Cichon, E A" uniqKey="Cichon E" first="E. A." last="Cichon">E. A. Cichon</name><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>CNRS-CRIN-INRIA-Lorraine, Campus Scientifique, BP 101, 54602 Villers-lès-Nancy, Cedex</wicri:regionArea><wicri:noRegion>Cedex</wicri:noRegion><wicri:noRegion>Cedex</wicri:noRegion></affiliation></author><author><name sortKey="Bittar, E Tahhan" sort="Bittar, E Tahhan" uniqKey="Bittar E" first="E. Tahhan" last="Bittar">E. Tahhan Bittar</name><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire de Mathematiques Discrètes et Informatique, Institut de Mathématiques-Informatique, Université Claude-Bernard, 43 Bd du 11 Novembre 1918, 69622 Villeurbanne, Cedex</wicri:regionArea><wicri:noRegion>Cedex</wicri:noRegion><wicri:noRegion>Cedex</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1998">1998</date><biblScope unit="volume">201</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="63">63</biblScope><biblScope unit="page" to="84">84</biblScope></imprint><idno type="ISSN">0304-3975</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Bittarl</term><term>Cartesian product</term><term>Characterise functions</term><term>Cichon</term><term>Computer science</term><term>Constant sequence</term><term>Constant subsequence</term><term>Constructive proof</term><term>Control function</term><term>Control information</term><term>Decomposition lemma</term><term>Finite alphabet</term><term>First paragraph</term><term>Fundamental sequence</term><term>Fundamental sequences</term><term>General case</term><term>Hardy hierarchies</term><term>Hardy hierarchy</term><term>Hierarchy</term><term>Higman</term><term>Higman function</term><term>Induction hypothesis</term><term>Initial part</term><term>Last component</term><term>Lecture notes</term><term>Lemma</term><term>Lemma dejine</term><term>Lemma guarantee</term><term>Length hierarchies</term><term>Limit ordinal</term><term>Majorisation properties</term><term>Mathematical logic</term><term>Naive argument</term><term>Natural number</term><term>Natural numbers</term><term>Ordinal</term><term>Ordinal term</term><term>Ordinal terms</term><term>Passenger sequence</term><term>Peano arithmetic</term><term>Present context</term><term>Present paper concerns theorem</term><term>Principal sequence</term><term>Principal subsequence</term><term>Product space</term><term>Product spaces</term><term>Recursive</term><term>Recursive functions</term><term>Same controls</term><term>Smallest relation</term><term>Subrecursive hierarchies</term><term>Subsequence</term><term>Such sequences</term><term>Tahhan</term><term>Tahhan bittar</term><term>Tahhan bittaritheoretical computer science</term><term>Tahhan bittarl</term><term>Terminal element</term><term>Terminal elements</term><term>Theoretical computer science</term><term>Totality</term><term>Transfinite induction</term><term>Worst case situation</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The present paper concerns Higman's theorem for strings generated over a finite alphabet. We give a constructive proof of this theorem and we construct and characterise functions which bound the lengths of bad sequences. These bounding functions are described by ordinal-recursive definitions and their characterisation is achieved with reference to Hardy hierarchies of numbertheoretic functions.</div></front></TEI><affiliations><list><country><li>France</li></country></list><tree><country name="France"><noRegion><name sortKey="Cichon, E A" sort="Cichon, E A" uniqKey="Cichon E" first="E. A." last="Cichon">E. A. Cichon</name></noRegion><name sortKey="Bittar, E Tahhan" sort="Bittar, E Tahhan" uniqKey="Bittar E" first="E. Tahhan" last="Bittar">E. Tahhan Bittar</name><name sortKey="Cichon, E A" sort="Cichon, E A" uniqKey="Cichon E" first="E. A." last="Cichon">E. A. Cichon</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002470 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Checkpoint/biblio.hfd -nk 002470 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Checkpoint
|type= RBID
|clé= ISTEX:2D8DBE8A7739405BF206BBC00B509404FF4EFBBC
|texte= Ordinal recursive bounds for Higman's theorem
}}
| This area was generated with Dilib version V0.6.33. |  |